package example2;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

//160. 相交链表
public class LeetCode160 {
    public static void main(String[] args) {

    }
}

//方法一：用hash表或列表存储一个链表已经遍历过的节点
class Solution160_1{
    List<ListNode160> list = new ArrayList<>();
    //用hashset更快
    Set<ListNode160> set = new HashSet<>();

    public ListNode160 getIntersectionNode(ListNode160 headA, ListNode160 headB) {
        if(headA == null || headB == null)  return null;
        while(headA != null){
            set.add(headA);
            headA = headA.next;
        }
        while(headB != null){
            if(set.contains(headB)){
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
}

//方法二：双指针遍历
/*
* 对于A、B两个链表，两个链表相交部分的长度为c，A不相交部分长度为m，B的不相交部分长度为n，
* 那么用a指针从A的头开始遍历，b指针从B的头开始遍历，当a和b走过的长度都达到m+n+c时，
* 此时，a和b所处的位置就是相交的节点，就算没有相交的节点，那么此时就返回null
* */
class Solution160_2{
    public ListNode160 getIntersectionNode(ListNode160 headA, ListNode160 headB) {
        if(headA == null || headB == null)  return null;
        ListNode160 a = headA;
        ListNode160 b = headB;
        while(true){
            if(a == b)  return a;
            if(a == null){
                a = headB;
            }else{
                a = a.next;
            }
            if(b == null){
                b = headA;
            }else{
                b = b.next;
            }
        }
    }
}

class ListNode160 {
    int val;
    ListNode160 next;
    ListNode160(int x) {
        val = x;
        next = null;
    }
}
